using System.Collections.Generic;

namespace DanMuHelper.Tools
{
    public static class ListUtil
    {
        /// <summary>
        /// 通过交换法快速删除index位置的元素，删除后数组元素位置变更
        /// </summary>
        /// <param name="list"></param>
        /// <param name="index"></param>
        /// <typeparam name="T"></typeparam>
        public static void FastRemoveAt<T>(this List<T> list, int index)
        {
            var lastPos = list.Count - 1;
            if (index != lastPos)
                list[index] = list[lastPos];
            list.RemoveAt(lastPos);
        }

        /// <summary>
        /// 通过交换法快速删除元素，删除后数组元素位置变更
        /// </summary>
        /// <param name="list"></param>
        /// <param name="index"></param>
        /// <typeparam name="T"></typeparam>
        public static void FastRemove<T>(this List<T> list, T item)
        {
            var pos = list.IndexOf(item);
            if (pos >= 0)
                list.FastRemoveAt(pos);
        }

        /// <summary>
        /// 删除单个匹配项
        /// </summary>
        /// <param name="list"></param>
        /// <param name="match"></param>
        /// <typeparam name="T"></typeparam>
        public static void FastRemove<T>(this List<T> list, System.Predicate<T> match)
        {
            var pos = list.FindIndex(match);
            if (pos >= 0)
                list.FastRemoveAt(pos);
        }

        /// <summary>
        /// 删除所有匹配项
        /// </summary>
        public static void FastRemoveAll<T>(this List<T> list, System.Predicate<T> match)
        {
            var n = list.Count;
            for (int pos = 0; pos < n;)
            {
                if (match(list[pos]))
                {
                    n--;
                    list.FastRemoveAt(pos);
                }
                else
                {
                    pos++;
                }
            }
        }

        /// <summary>
        /// 添加（去重）
        /// </summary>
        /// <param name="list"></param>
        /// <param name="item"></param>
        /// <typeparam name="T"></typeparam>
        public static void AddUniq<T>(this List<T> list, T item)
        {
            if (!list.Contains(item))
                list.Add(item);
        }

        /// <summary>
        /// 添加（去重）
        /// </summary>
        public static void AddRangeUniq<T>(this List<T> list, IEnumerable<T> range)
        {
            foreach (var it in range)
                list.AddUniq(it);
        }

        public static void AddRangeUniq<T>(this List<T> list, T[] range)
        {
            var n = range?.Length ?? 0;
            for (int i = 0; i < n; i++)
                list.AddUniq(range[i]);
        }

        public static void AddRangeUniq<T>(this List<T> list, List<T> range)
        {
            var n = range?.Count ?? 0;
            for (int i = 0; i < n; i++)
                list.AddUniq(range[i]);
        }

        /// <summary>
        /// 弹出末尾的元素
        /// </summary>
        /// <param name="list"></param>
        /// <typeparam name="T"></typeparam>
        /// <returns></returns>
        public static T PopLast<T>(this List<T> list)
        {
            var pos = list.Count - 1;
            var reg = list[pos];
            list.RemoveAt(pos);
            return reg;
        }

        /// <summary>
        /// 交换两个元素的位置
        /// </summary>
        /// <param name="list"></param>
        /// <param name="idx1"></param>
        /// <param name="idx2"></param>
        /// <typeparam name="T"></typeparam>
        public static void Swap<T>(this List<T> list, int idx1, int idx2)
        {
            if (idx1 != idx2)
            {
                // var backup1 = list[idx1];
                // list[idx1] = list[idx2];
                // list[idx2] = backup1;
                (list[idx1], list[idx2]) = (list[idx2], list[idx1]);
            }
        }

        public delegate bool Condition<T>(T a, T b);

        public static void SortList<T>(this List<T> array, Condition<T> condition)
        {
            for (int j = 0; j < array.Count - 1; j++)
            {
                for (int i = 0; i < array.Count - 1 - j; i++)
                {
                    if (condition(array[i], array[i + 1]))
                    {
                        T temp = array[i];
                        array[i] = array[i + 1];
                        array[i + 1] = temp;
                    }
                }
            }
        }

        public static void QuickSortList<T>(this List<T> array, Condition<T> condition)
        {
            QuickSort(array, 0, array.Count - 1, condition);
        }

        private static void QuickSort<T>(List<T> array, int left, int right, Condition<T> condition)
        {
            if (left < right)
            {
                int pivotIndex = Partition(array, left, right, condition);
                QuickSort(array, left, pivotIndex - 1, condition);
                QuickSort(array, pivotIndex + 1, right, condition);
            }
        }

        private static int Partition<T>(List<T> array, int left, int right, Condition<T> condition)
        {
            T pivot = array[right];
            int i = left - 1;

            for (int j = left; j < right; j++)
            {
                if (condition(array[j], pivot))
                {
                    i++;
                    (array[j], array[i]) = (array[i], array[j]);
                }
            }
            (array[right], array[i + 1]) = (array[i + 1], array[right]);
            return i + 1;
        }
    }
}
